/*
 * @lc app=leetcode.cn id=2187 lang=cpp
 *
 * [2187] 完成旅途的最少时间
 */

// @lc code=start
class Solution
{
public:
    long long isValidate(vector<int> &time, long long n)
    {
        long long res = 0;
        for (auto x : time)
        {
            res += n / x;
        }
        return res;
    }
    long long minimumTime(vector<int> &time, int totalTrips)
    {
        long long l = 0, r = 1LL * totalTrips * time[0], mid;
        for (auto x : time)
        {
            r = min(r, 1LL * totalTrips * x);
        }
        while (l < r)
        {
            mid = l + (r - l) / 2;
            if (isValidate(time, mid) < totalTrips)
            {
                l = mid + 1;
            }
            else
            {
                r = mid;
            }
        }

        return l;
    }
};
// @lc code=end
